package com.example.question.list.list2;

import com.example.question.list.list1.List;
import com.example.question.list.list1.ListNode;

import java.util.ArrayList;

/**
 * @Date 2023-07-08
 * @Author Jonathan
 */
public class Code03_86 {
    public static void main(String[] args) {
        ListNode listNode = List.createList(new int[]{1, 4, 3, 0, 2, 5, 2});
        Code03_86 code = new Code03_86();
        ListNode partition = code.partition(listNode, 3);
        System.out.println(partition);

    }

    /**
     * 找到第一个大于x的节点
     */
    public ListNode partition1(ListNode head, int x) {
        ListNode dummy = new ListNode(1000, head);
        ListNode cur = dummy.next;
        ListNode pre = dummy;
        ListNode newDummy = new ListNode(-1);
        ListNode small = newDummy;
        while (cur != null) {
            if (cur.val < x) {
                ListNode lessNode = cur;
                pre.next = pre.next.next;
                cur = lessNode.next;
                lessNode.next = null;
                small.next = lessNode;
                small = small.next;
            } else {
                cur = cur.next;
                pre = pre.next;
            }
        }
        small.next = dummy.next;
        return newDummy.next;
    }

    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(1000, head);
        ListNode cur = dummy.next;
        ListNode pre = dummy;
        java.util.List<ListNode> lessXList = new ArrayList<>();

        while (cur != null) {
            if (cur.val < x) {
                ListNode lessNode = cur;
                pre.next = pre.next.next;
                cur = lessNode.next;
                lessNode.next = null;
                lessXList.add(lessNode);
            } else {
                cur = cur.next;
                pre = pre.next;
            }
        }
        if (lessXList.isEmpty()) {
            return dummy.next;
        }
        ListNode newHead = lessXList.get(0);
        cur = newHead;
        for (int i = 1; i < lessXList.size(); i++) {
            cur.next = lessXList.get(i);
            cur = cur.next;
        }
        cur.next = dummy.next;
        return newHead;
    }
}
